package com.fanco.learn_datastruct_leetcode.leetcode;

import java.util.*;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *  左括号必须用相同类型的右括号闭合。
 *  左括号必须以正确的顺序闭合。
 * @author qiaowang 2021/7/6
 */
public class Day12 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValid("(("));
    }

    private static class Solution {
        public boolean isValid(String s) {
            int n = s.length();
            if (n % 2 == 1) {
                return false;
            }
            Map<Character, Character> map = new HashMap<Character, Character>(){
                {
                    put(')', '(');
                    put(']','[');
                    put('}','{');

                }
            };

            Deque characterQueue = new LinkedList();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                /**
                 * 遍历字符串
                 * 当前字符可以在map中找到，说明是闭合符号，这时候找栈顶的元素
                 * 是否和它能匹配，如果可以，则继续循环，不可以直接返回false
                 */
                if(map.containsKey(ch)) {
                    // 栈空 或者 栈顶元素不匹配都不可以
                    // peek 获取栈顶的元素，最后放进去的元素。
                    if (characterQueue.isEmpty() || characterQueue.peek() != map.get(ch)) {
                        return false;
                    }
                    characterQueue.pop();
                } else {
                    // 不存在入栈
                    characterQueue.push(ch);
                }
            }

            return characterQueue.isEmpty();


        }

    }
}
